package com.example.demo.hot100;

/**
 * @Classname no9
 * @Description
 * @Date 2023/12/19 16:03
 * @Created by jyl
 *
 * 删除排序链表中的重复元素II
 * 给定一个排序链表，删除所有重复的元素，使得每个元素最多出现两次。
 *
 *
 * 解：使用两个指针 prev 和 current 来遍历链表。对于每个节点，我们寻找其连续重复节点的范围，然后根据出现次数决定是否删除重复节点。最后，返回处理后的链表
 */
public class no9 {


    public static void main(String[] args) {
        RemoveDuplicatesFromSortedListII solution = new RemoveDuplicatesFromSortedListII();

        // 创建一个有序链表：1 -> 1 -> 1 -> 2 -> 3
        ListNode head = new ListNode(1);
        head.next = new ListNode(1);
        head.next.next = new ListNode(1);
        head.next.next.next = new ListNode(2);
        head.next.next.next.next = new ListNode(3);

        // 删除重复元素
        ListNode result = solution.deleteDuplicates(head);

        // 打印结果链表
        printList(result);
    }


    static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }

    public static class RemoveDuplicatesFromSortedListII {

        public ListNode deleteDuplicates(ListNode head) {
            // 创建一个虚拟头节点，简化边界情况处理
            ListNode dummy = new ListNode(0);
            dummy.next = head;
            ListNode prev = dummy;
            ListNode current = head;

            while (current != null) {
                // 寻找连续重复节点的范围
                while (current.next != null && current.val == current.next.val) {
                    current = current.next;
                }

                // 如果出现次数超过两次，删除重复节点
                if (prev.next != current) {
                    prev.next = current.next;
                } else {
                    prev = prev.next;
                }

                current = current.next;
            }

            return dummy.next;
        }
    }

    // 辅助方法：打印链表
    private static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
    }
}
